public class project {

}
class Solution {
    public int maxProfit(int[] prices) {
        int max=0;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<prices.length;i++){
            if(prices[i]<min){
                min=prices[i];
            }
            else if(prices[i]-min>max){
                max=prices[i]-min;
            }
        }
        return max;
    }
}










class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int i=0;
        int[] hash=new int[1001];
        for(int n : arr1){
            hash[n]++;
        }
        for(int n : arr2){
            while(hash[n]>0){
                arr1[i++]=n;
                hash[n]--;
            }
        }
        for(int j=0;j<hash.length;j++){
            while(hash[j]>0){
                arr1[i++]=j;
                hash[j]--;
            }
        }
        return arr1;
    }
}













class Solution {
    public int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length;
        while(left<right){
            int mid=(left+right)/2;
            if(nums[mid]>=target){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
}










class Solution {
    public int mySqrt(int x) {
        if(x<=1){
            return x;
        }
        int left=1;
        int right=x;
        while(left<=right){
            int mid=left+(right-left)/2;
            long tmp=(long)mid*mid;
            if(tmp==x){
                return mid;
            }else if(tmp>x){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return left-1;
    }
}









class Solution {
    public int purchasePlans(int[] nums, int target) {
        int sum=0;
        Arrays.sort(nums);
        int left=0;
        int right=nums.length-1;
        while(left<right){
            int mid=nums[left]+nums[right];
            if(mid>target){
                right--;
            }else{
                sum+=right-left;
                left++;
            }
            sum%=1000000007;
        }
        return sum%1000000008;
    }
}